package datastructure.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/*
    边节点
 */
class ArcNode {
    int adjvex;
    ArcNode nextarc;
    int weight;
}

class VNode {
    String[] data;
    ArcNode firstarc;
}

public class AdjGraphClass {
    final int MAXV = 100;
    final int INF = Integer.MAX_VALUE;
    VNode[] adjlist;
    int n, e;

    public AdjGraphClass() {
        adjlist = new VNode[MAXV];
        for (int i = 0; i < MAXV; i++) {
            adjlist[i] = new VNode();
        }
    }

    public void createAdjGraph(int[][] a, int n, int e) {
        this.n = n;
        this.e = e;
        for (int i = 0; i < n; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (a[i][j] != INF && a[i][j] != 0) {
                    ArcNode arcNode = new ArcNode();
                    arcNode.weight = a[i][j];
                    arcNode.adjvex = j;
                    arcNode.nextarc = adjlist[i].firstarc;
                    adjlist[i].firstarc = arcNode;
                }
            }
        }
    }

    public void dispAdjGraph() {        //输出图的邻接表
        ArcNode p;
        for (int i = 0; i < n; i++) {
            System.out.printf("  [%d]", i);
            p = adjlist[i].firstarc;        //p指向第一个邻接点
            while (p != null) {
                System.out.printf("->(%d,%d)", p.adjvex, p.weight);
                p = p.nextarc;            //p移向下一个邻接点
            }
            System.out.println("->∧");
        }
    }

    /*
    求顶点的入度和出度
 */
    public int[] getDegree(int v) {
        int[] degree = {0, 0};
        ArcNode p = adjlist[v].firstarc;
        while (p != null) {
            degree[0]++;
            p = p.nextarc;
        }

        ArcNode q;
        for (int i = 0; i < n; i++) {
            q = adjlist[i].firstarc;
            while (q != null && q.adjvex == v) {
                degree[1]++;
                q = q.nextarc;
            }
        }

        return degree;
    }

    public static void DFS(AdjGraphClass graph, int v, int[] visited) {
        int vex;
        System.out.print(v + "->");
        visited[v] = 1;
        ArcNode p = graph.adjlist[v].firstarc;
        while (p != null) {
            vex = p.adjvex;
            if (visited[vex] == 0) {
                DFS(graph, vex, visited);
            }
            p = p.nextarc;
        }
    }

    public static void BFS(AdjGraphClass graph, int v, int[] visited) {
        System.out.print(v + "->");
        visited[v] = 1;
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        ArcNode p;
        while (!q.isEmpty()) {
            v = q.poll();
            p = graph.adjlist[v].firstarc;
            while (p != null) {
                if (visited[p.adjvex] == 0) {
                    q.offer(p.adjvex);
                    System.out.print(p.adjvex + "->");
                    visited[p.adjvex] = 1;
                }
                p = p.nextarc;
            }
        }
    }

    public static void main(String[] args) {
        int[][] data = {
                {0, 8, Integer.MAX_VALUE, 5, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 6},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 9, 0, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };
        AdjGraphClass adj = new AdjGraphClass();
        adj.createAdjGraph(data, data.length, 5);
        adj.dispAdjGraph();
        int[] degree = adj.getDegree(0);
        System.out.println(Arrays.toString(degree));

        int[] visited = new int[data.length];
        Arrays.fill(degree, 0);
        //DFS(adj, 0, visited);
        BFS(adj, 0, visited);
    }
}
